package com.le.enhance.class2;

import org.junit.Test;
import java.util.LinkedList;
/**
 * 最大值 - 最小值 <= num 的子数组数量   O(n)
 */
public class Code_02_MaxChildrenArrayNum {

    // 暴力方法 for循环
    public static int getArray1(int[] arr, int num) {
        int res = 0;
        for (int start = 0; start < arr.length; start++) {
            for (int end = start; end < arr.length; end++) {
                if (isValid(arr, start, end, num)) {
                    res++;
                }else {
                    break;
                }
            }
        }
        return res;
    }

    private static boolean isValid(int[] arr, int start, int end, int num) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = start; i <= end; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }
        return max - min <= num;
    }

    /**
     * 思路:
     * 假设: 0--x之间满足, 那么0-x之间任何位置都满足, res = x-0
     * 继续判断 1-x+1---->之间
     * @param arr
     * @param num
     * @return
     */
    public static int getArrayByLinked(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        LinkedList<Integer> qMin = new LinkedList<>();
        LinkedList<Integer> qMax = new LinkedList<>();
        int i = 0;
        int j = 0;
        int res = 0;
        while (i < arr.length) {
            while (j < arr.length) {
                while (!qMin.isEmpty() && arr[qMin.peekLast()] >= arr[j]) {
                    qMin.pollLast();
                }
                qMin.addLast(j);
                while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[j]) {
                    qMax.pollLast();
                }
                qMax.addLast(j);
                if (arr[qMax.getFirst()] - arr[qMin.getFirst()] > num) {
                    break;
                }
                j++;
            }
            if (qMin.peekFirst() == i) { // 更新最小值
                qMin.pollFirst();
            }
            if (qMax.peekFirst() == i) { // 更新最大值
                qMax.pollFirst();
            }
            res += j - i;
            i++;
        }
        return res;
    }


    @Test
    public void test1() {
        int[] arr = {0, 1, 3, 5,6};
        int res = getArray1(arr, 3);
        System.out.println("res: "+res);
        int res1 = getArrayByLinked(arr, 3);
        System.out.println("res1: "+res1);
    }
}
